백준 5639번

이진 검색 트리

Posted by ChoiCube84 on August 24, 2023 · 11 mins read

백준 5639번

오늘 풀어본 문제는 백준의 5639번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 4

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

  • 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.

  • 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.

  • 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

Binary Search Tree Example

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 $50\ 30\ 24\ 5\ 28\ 45\ 98\ 52\ 60$ 이고, 후위 순회 결과는 $5\ 28\ 24\ 45\ 30\ 60\ 52\ 98\ 50$ 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 $10^6$ 보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 $10,000$ 개 이하이다. 같은 키를 가지는 노드는 없다.

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

풀이과정

1번째 시도

이 문제는 이진 검색 트리 (Binary Search Tree, a.k.a. BST) 에서 삽입 과정과 전위 순회를 구현하는 문제이다. 데이터구조 수업 때 배우고 직접 구현했던 자료 구조로, 그냥 그 코드를 긁어와서 조금만 손본 뒤 제출해도 되었겠지만, 다음과 같은 이유로 다시 직접 구현하기로 했다.

  1. 옛날 생각이 나서 그 떄의 추억에 잠기기 위해 직접 구현하였다.
  2. B-Tree 프로젝트를 통해 데이터구조 구현에 자신감이 붙어 직접 구현하였다.
  3. 나중에 재활용하기 위해서 제대로 짜기 위해 직접 구현하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

template <typename T>
class BinarySearchTree {
private:
	struct Node {
		Node* left;
		Node* right;
		T value;

		Node(const T& value) : left(nullptr), right(nullptr), value(value) {}
	};

	Node* head;

	void preOrder(Node* currentNode, std::ostringstream& oss, const char& separator) {
		oss << currentNode->value << separator;

		if (currentNode->left != nullptr) {
			preOrder(currentNode->left, oss, separator);
		}

		if (currentNode->right != nullptr) {
			preOrder(currentNode->right, oss, separator);
		}
	}

	void inOrder(Node* currentNode, std::ostringstream& oss, const char& separator) {
		if (currentNode->left != nullptr) {
			inOrder(currentNode->left, oss, separator);
		}

		oss << currentNode->value << separator;

		if (currentNode->right != nullptr) {
			inOrder(currentNode->right, oss, separator);
		}
	}

	void postOrder(Node* currentNode, std::ostringstream& oss, const char& separator) {
		if (currentNode->left != nullptr) {
			postOrder(currentNode->left, oss, separator);
		}

		if (currentNode->right != nullptr) {
			postOrder(currentNode->right, oss, separator);
		}

		oss << currentNode->value << separator;
	}

public:
	BinarySearchTree() : head(nullptr) {}

	~BinarySearchTree() {
		if (head != nullptr) {
			std::stack<Node*> s;
			s.push(head);

			while (!s.empty()) {
				Node* currentNode = s.top();
				s.pop();

				if (currentNode->left != nullptr) {
					s.push(currentNode->left);
				}
				if (currentNode->right != nullptr) {
					s.push(currentNode->right);
				}

				delete currentNode;
			}
		}
	}

	void insert(const T& value) {
		if (head == nullptr) {
			head = new Node(value);
		}
		else {
			Node* currentNode = head;
			Node* parentNode = nullptr;

			while (currentNode != nullptr) {
				parentNode = currentNode;
				if (value < currentNode->value) {
					currentNode = currentNode->left;
				}
				else {
					currentNode = currentNode->right;
				}
			}

			if (value < parentNode->value) {
				parentNode->left = new Node(value);
			}
			else {
				parentNode->right = new Node(value);
			}
		}
	}

	void remove(const T& value) {
		// TODO: Implement this later
	}

	bool search(const T& value) {
		Node* currentNode = head;

		while (currentNode != nullptr) {
			if (value < currentNode->value) {
				currentNode = currentNode->left;
			}
			else if (value > currentNode->value) {
				currentNode = currentNode->right;
			}
			else {
				return true;
			}
		}

		return false;
	}

	std::string preOrder(const char& separator = ' ') {
		std::ostringstream oss;

		if (head != nullptr) {
			preOrder(head, oss, separator);
		}

		std::string result = std::move(oss).str();
		if (!result.empty()) {
			result.pop_back();
		}
		return result;
	}

	std::string inOrder(const char& separator = ' ') {
		std::ostringstream oss;

		if (head != nullptr) {
			inOrder(head, oss, separator);
		}

		std::string result = std::move(oss).str();
		if (!result.empty()) {
			result.pop_back();
		}
		return result;
	}

	std::string postOrder(const char& separator = ' ') {
		std::ostringstream oss;

		if (head != nullptr) {
			postOrder(head, oss, separator);
		}

		std::string result = std::move(oss).str();
		if (!result.empty()) {
			result.pop_back();
		}
		return result;
	}
};

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	BinarySearchTree<int> bst;

	int number;
	while (cin >> number) {
		bst.insert(number);
	}

	cout << bst.postOrder('\n');

	return 0;
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

간만에 데이터구조 과제를 하는 느낌을 받았다. 실제 과제는 구현해야할 것도 많고 필요한 기능을 전부 구현해야 했지만, 이 문제는 삽입과 전위 순회만 필요한 문제여서 삭제같이 구현하기 귀찮은 기능들은 뒤로 미뤄두는 식으로 끝냈기 때문에 금방 끝났다.

내가 구현한 BinarySearchTree 는 여기서2 확인할 수 있다. 나중에 필요하면 BinarySearchTree::remove 함수를 구현해서 업데이트 하도록 하겠다.

오늘의 PS는 여기까지!


1: https://www.acmicpc.net/problem/5639
2: https://github.com/ChoiCube84/baekjoon-solutions/blob/main/C%2B%2B/custom_data_structures/binary_search_tree.hpp